The present invention relates in general to a method and system for data processing in general and, in particular, to a method and system for bus arbitration based on variable priority and fairness protocols.
A computer system typically includes several types of buses, such as system bus, local buses, and peripheral buses. Various electronic circuit devices and components are connected with each other via these buses such that intercommunication may be possible among all of these devices and components.
In general, a central processing unit (CPU) is attached to a system bus, over which the CPU communicates directly with a system memory that is also attached to the system bus. A local bus is intended for connecting certain highly integrated peripheral components on the same bus as the CPU. One such local bus is known as the Peripheral Component Interconnect (PCI) bus. Under the PCI local bus standard, peripheral components can directly connect to a PCI local bus without the need for glue logic. Thus, PCI provides a bus standard on which high-performance peripheral devices, such as graphics devices and hard disk drives, can be coupled to the CPU, thereby permitting these high-performance peripheral devices to avoid the general access latency and the bandwidth constraints that are associated with a peripheral bus. A peripheral bus such as an Industry Standard Architecture (ISA) bus, is for connecting various peripheral devices to the computer system. These peripheral devices typically include input/output (I/O) devices such as a keyboard, floppy drives, and printers.
Generally, each system bus, local bus, and peripheral bus utilizes an independent set of protocols (or rules) to conduct data transfers between various devices attached to it. Each of these protocols is designed into a bus directly and is commonly referred to as the xe2x80x9carchitecturexe2x80x9d of the bus. In a data transfer between different bus architectures, data being transferred from the first bus architecture may not be in a form that is usable or intelligible by the receiving second bus architecture. Accordingly, a mechanism is developed for xe2x80x9ctranslatingxe2x80x9d data that are required to be transferred from one bus architecture to another. This translation mechanism is normally contained in a hardware device in the form of a bus-to-bus bridge (or interface) through which the two different types of buses are connected.
Incidentally, various bus-to-bus bridges have been designed to match the communication protocol of one bus with that of another in order to permit system-wide communications between devices on different buses. For example, a bus-to-bus bridge connecting between a system bus and a PCI local bus is called a PCI host bridge. The PCI host bridge contains all the logic and hardware for translating data communications between the system bus and the PCI local bus, and ensures that data is transferred between these two buses intelligibly.
If multiple devices connected to the different buses gained access to the CPU or even a local bus at the same time, chaos would result. Chaos is avoided by introducing one or more bus masters into the system. A bus master controls access to the bus. In other words, it initiates and controls all bus requests.
Deciding which device or bus master to use the bus next is called bus arbitration. In a bus arbitration scheme, a device (or the processor) wanting to use the bus signals a bus request. In response, at a later point in time the arbiter sends a grant signal to the device. After the grant is received, the device can use the bus. The device later signals to the arbiter that the bus is no longer required. The arbiter can then grant the bus to another device.
Arbitration schemes usually try to balance two factors in choosing which device to grant the bus. First, each device has a bus priority, and the highest-priority devices should be serviced first. Second, to assure that no device, even with low priority, is never completely locked out, most I/O buses such as PCI also require that the arbiter implement some kind of fairness protocol. The intent of a fairness protocol is to assure that all devices receive a turn on the bus. For instance, one conventional fairness protocol is a round robin scheme. Under a round robin fairness protocol, a device which has just completed a bus operation is not granted access to the bus for a second operation until all the requesting devices have first been granted access to the bus.
Even though a bus may provide a fairness protocol in the arbiter(s) that control access to the bus, acceptable access to the bus can be effectively denied to a device or devices by other high performance devices. This is an unexpected problem that fairness protocols were intended to avoid. The problem is that of xe2x80x9cbeatxe2x80x9d frequencies that interfere with a device""s access to the bus. The concept of this xe2x80x9cbeatxe2x80x9d frequency will be described below.
Some buses such as PCI provide a performance feature usually referred to as xe2x80x9cbackoffxe2x80x9d capability that allows a device to disconnect from the bus if it is not able to handle the request at that time. This capability in PCI is referred to as Retry. If a PCI device is not able to handle a request when it occurs the target of the request can issue a xe2x80x9cRetryxe2x80x9d which indicates to the master that issued the request on the bus to try again later.
For PCI, the typical platform provides a PCI host bridge to provide bus synchronization between the system bus and the PCI bus. The platform may also provide a number of PCI-to-PCI bus bridges to provide additional PCI bus segments. Usually each PCI bus segment will have its own arbiter (with fairness protocol). Each bridge usually has posting buffers for temporary buffering of bus transactions as these transactions flow through the bridge in both directions (primary side to secondary side, and secondary side to primary of a bridge).
The way a beat frequency can deny a device effective access to the bus involves interaction between the set of buffers in a bridge, the bridge arbiter, and the bus traffic by devices on the bus. For example, assume a bus under a PCI host bridge or PCI-to-PCI bridge has a round-robin fairness protocol to four devices under the bridge (Device A, Device B, Device C, and Device D). Also assume the bridge is assigned the highest priority (priority 0), Device A is assigned the next highest priority (priority 1), Device B is assigned the next highest priority (priority 2), Device C is assigned the next highest priority (priority 3), and Device D is assigned the next highest priority (priority 4). If all devices ask for the bus at the same time, the fairness protocol will assure that each devices get a chance to try to utilize the bus. The arbitration priority, in this example, simply determines the order in which the devices get a turn to try to utilize the bus. In this example when all devices request use of the bus, the bridge is granted first access, then Devices A to D in sequence. Under this scheme, both Device A and B could get a turn on the bus and fill up the bridge""s buffers such that when Device C gets on the bus, Device C gets a Retry because the bridge""s buffers are full. Eventually, the bridge empties out some of the buffers as transactions on the other side of the bridge. Then Devices D, A and B get turns on the bus, again filling the buffers. When Device C gets its rotating turn on the bus again, it again receives a Retry because the bridge""s buffers are full again. A beat frequency can occur such that each time a specific device gets a turn on the bus it is turned away with a Retry (or equivalent, depending on the bus type) because other devices keep filling up the bridge buffers. When the number of Retries are relatively high, the device can overrun or underrun resulting in significant performance losses from software detecting the overrun or underrun and repeating the operation.
Simply adding more buffers to the bridge only changes the amount of data that Devices A, B, and D need to transfer to produce the xe2x80x9cbeatxe2x80x9d frequency problem. Adding a very large number of buffers should eliminate the problem but this would be impractical because it is too expensive.
What is needed, therefore, is a scheme that changes the arbitration priority level so that the rotation sequence changed to increase the probability that each device would get a fairness turn on the bus without interference from a beat frequency.
The previously mentioned needs are fulfilled with the present invention. Accordingly, there is provided, in a first form, a computer system having a local bus which communicates to a CPU through a bus bridge, wherein the bus bridge contains a bus arbiter for controlling and prioritizing bus request signals from a plurality of bus devices connected to the bus. The granting of the bus is based on each devices priority, previous access within a fairness cycle, and retry history. Also disclosed is a bus arbiter containing fairness logic for controlling and prioritizing bus request signals based on a predetermined priority of each bus device and each bus device""s prior access within a fairness cycle. The arbiter contains logic for granting control of the bus to a bus device based on the fairness logic.
The invention also includes a method for bus arbitration in a computer system comprising the steps of receiving bus request signals from several bus devices, starting a fairness cycle, selecting a single bus device from the bus devices based on the highest priority of bus devices with respect to other devices and whether or not fairness flag is set for the bus device. If the flag is set, then the priority is reduced. Flags are only set if the devices are granted access to the bus and do not receive a retry signal.